STARK based accumulator

MiMCを用いたinclusionとexclusionを証明できるaccumulator

ここでのround constantsは毎回を考え、root of unity = 512とする。

つまり、$ x -> x^3 + dが512回となる。

MiMC digestから特定のラウンドの$ dを見つけ出すことはほぼ不可能。

要は、MiMCの一方向性を強調するためにSTARKをハッシュ化の方向で用いている。

ここで以下のようにパラメタを設定する。

A: accumulator state

W: witness (constraintを満たすべき512個の値シーケンス）

M: loop counter

P: puroduct trace

.$ w: root of unity

x: inclusion or exclusionを証明したい値

transition constraintsは以下のように設定する。

M{i] = 1 or W{i] = W{i - 1]

Wは512の倍数でのみ変更可能

M{i] = M{i - 1] * $ w

loop counterのインクリメント。512ステップごとに1に戻る

A{i] = A{i - 1]^3 + W{i]

witnessに一致しているか

P{i] = P{i - 1] * (x - W{i - 1])

boundary constraintsは以下の通り。

A{0]がaccumulatorの初期値

A{n]がaccumulatorのラスト状態

P{0] = 1

つまり、inclusionの場合はxと一致するwitnessが存在するのでPがゼロになるのに対し、exclusionの場合はゼロにならない。